from .hash_map_base import HashMapBase


class ProbeHashMap(HashMapBase):
    """使用含线性探测的开发寻址实现的HashMap"""
    _AVAIL = object()

    def _is_available(self, j):
        return self._table[j] is None or self._table[j] is ProbeHashMap._AVAIL

    def _find_slot(self, j, k):
        """
        Search for key k in bucket at index j
        :param j:
        :param k:
        :return:
        """
        first_avild = None
        while True:
            if self._is_available(j):
                if first_avild is None:
                    first_avild = j           #mark this as first avail
                if self._table[j] is None:
                    return (False, first_avild) # search failed
            elif k == self._table[j]._key:      #found a match
                return (True, j)
            j = (j + 1)%len(self._table)


    def _bucket_getitem(self, j, k):
        found, j = self._find_slot(j, k)
        if not found:
            raise KeyError("key error: {}".format(repr(k)))
        return self._table[j]._value

    def _bucket_setitem(self, j, k, v):
        found, j = self._find_slot(j, k)
        if not found:
            self._table[j] = self._Item(k, v)
            self._n += 1
        else:
            set._table[j]._value = v

    def _bucket_delitem(self, j, k):
        found, j = self._find_slot(j, k)
        if not found:
            raise KeyError("key error: {}".format(repr(k)))
        self._table[j] = ProbeHashMap._AVAIL

    def __iter__(self):
        for j in range(len(self._table)):
            if not self._is_available(j):
                yield self._table[j]._key